
def linear_segment_intersection(segments_list): # each item in the list is a tuple of 2 numbers - start x and end x
    xstart_points = []
    xend_points = []
    
    for segment in segments:
        xstart, xend = segment
        xstart_points.append((xstart, segment))
        xend_points.append((xend, segment))
    
    
    xstart_points.sort(key = itemgetter(0))
    xend_points.sort(key = itemgetter(0))
    
    intersection_stack = []
    intersections = []
    i = 0
    j = 0
    while i < len(xstart_points) and j < len(xend_points):
        xstart_coord, xstart_segment = xstart_points[i]
        xend_coord, xend_segment = xend_points[j]
        if xstart_coord < xend_coord:
            intersection_stack.append(xstart_segment)
            i += 1
        elif xstart_coord > xend_coord:
            temp_stack = []
            intersections.append((xend_segment, temp_stack))
            while intersection_stack[-1][0] < xend_coord:
                temp_stack.append(intersection_stack.pop())
                
            # assert intersection_stack[-1] == xend_segment
            # so pop it
            intersection_stack.pop()
            
            # add the rest of the removed segments
            intersection_stack += temp_stack
            
            j += 1
            
    return intersections
    
def y_at(segment, x):
    p1 = segment.p1
    p2 = segment.p2
    
    if p2.x == p1.x: return (p1.y + p2.y) / 2
    
    f = (x - p1.x) / (p2.x - p1.x)
    
    return f * (p2.y - p1.y) + p1.y
    
class SweepingLineDatabase(object):
    def __init__(self):
        super(SweepingLineDatabase, self).__init__()
        
        self.active_segments = []
        
    def binsearch(self, segment, x):
        return binsearch(self.active_segments, segment, cmpfunc = lambda a, b: cmp(y_at(a, x), y_at(b, x)))
        
    def above(self, segment, x):
        i = self.binsearch(segment, x)
        if i == 0: return None
        return self.active_segments[i - 1]
        
    def below(self, segment, x):
        i = self.binsearch(segment, x)
        if i == len(self.active_segments) - 1: return None
        return self.active_segments[i + 1]
        
    def insert(self, segment, x):
        i = self.binsearch(segment, x)
        self.active_segments.insert(segment, i)
        
    def remove(self, segment):
        i = self.binsearch(segment, x)
        del self.active_segments[i]
        
def segment_intersections(segments):
    xstart_points = []
    xend_points = []
    
    for segment in segments:
        xstart, xend = segment.p1.x, segment.p2.x
        ystart, yend = segment.p1.y, segment.p2.y
        xstart_points.append(((xstart, ystart), segment))
        xend_points.append(((xend, yend), segment))
    
    
    xstart_points.sort(key = itemgetter(0))
    xend_points.sort(key = itemgetter(0))
    
    sld = SweepingLineDatabase()
    
    intersections = []
    
    i = 0
    j = 0
    while i < len(xstart_points) and j < len(xend_points):
        (xstart_coord, ystart_coord), xstart_segment = xstart_points[i]
        (xend_coord, yend_coord), xend_segment = xend_points[j]
        if xstart_coord < xend_coord:
            sld.insert(xstart_segment)
            above_segment = sld.above(xstart_segment, xstart_coord)
            if above_segment is not None:
                if segments_intersect(above_segment, xstart_segment):
                    if not point_on_segment(above_segment, xstart_segment.p1) and not point_on_segment(above_segment, xstart_segment.p2):
                        intersections.append((xstart_segment, above_segment))
            below_segment = sld.below(xstart_segment, xstart_coord)
            if below_segment is not None:
                if segments_intersect(below_segment, xstart_segment):
                    if not point_on_segment(below_segment, xstart_segment.p1) and not point_on_segment(below_segment, xstart_segment.p2):
                        intersections.append((xstart_segment, below_segment))
            i += 1
        elif xstart_coord > xend_coord:
            above_segment = sld.above(xend_segment, xend_coord)
            below_segment = sld.below(xend_segment, xend_coord)
            if above_segment is not None and below_segment is not None:
                if segments_intersect(above_segment, below_segment):
                    intersections.append((above_segment, below_segment))
                    
            sld.remove(xend_segment)
            
        
            j += 1
        elif xstart_coord == xend_coord:
            if ystart_coord < yend_coord:
                sld.insert(xstart_segment)
                above_segment = sld.above(xstart_segment, xstart_coord)
                if above_segment is not None:
                    if segments_intersect(above_segment, xstart_segment):
                        if not point_on_segment(above_segment, xstart_segment.p1) and not point_on_segment(above_segment, xstart_segment.p2):
                            intersections.append((xstart_segment, above_segment))
                below_segment = sld.below(xstart_segment, xstart_coord)
                if below_segment is not None:
                    if segments_intersect(below_segment, xstart_segment):
                        if not point_on_segment(below_segment, xstart_segment.p1) and not point_on_segment(below_segment, xstart_segment.p2):
                            intersections.append((xstart_segment, below_segment))
                i += 1
            elif ystart_coord > yend_coord:
                above_segment = sld.above(xend_segment, xend_coord)
                below_segment = sld.below(xend_segment, xend_coord)
                if above_segment is not None and below_segment is not None:
                    if segments_intersect(above_segment, below_segment):
                        intersections.append((above_segment, below_segment))
                        
                sld.remove(xend_segment)
                
            
                j += 1
            
    return intersections
    